#pragma once

#include <iostream>
#include <valarray>
#include "vector"
#include <cassert>
#include <functional>
#include "algorithm"
#include "set"
#include "array"
#include <numeric> // 包含 std::accumulate
#include "tuple" //方便解包
#include "stack" //回溯算法
class Cover{
private:
    int m_row,m_col;
public:
    std::set<int> setRow,setCol;
    size_t CoverZeroNum = 0;
    Cover() = default;
    Cover(int row,int col)
    {
        m_col = col;
        m_row = row;
    }
    [[nodiscard]] size_t size() const {
        return setRow.size() + setCol.size();
    }

    [[nodiscard]] std::tuple<std::vector<int>,std::vector<int>> diff() const
    {
        // 返回 0:m_Row-1 与 0:m_col-1 差分后的结果
        std::vector<int> x(m_row),y(m_col);
        std::iota(x.begin(),x.end(),0);
        std::iota(y.begin(),y.end(),0);
        std::vector<int> diff_x,diff_y;
        std::set_difference(x.begin(),x.end(),setRow.begin(),setRow.end(),std::back_inserter(diff_x));
        std::set_difference(y.begin(),y.end(),setCol.begin(),setCol.end(),std::back_inserter(diff_y));

        return std::tie(diff_x,diff_y);
    }



    void insert(const Cover & cover2){
        CoverZeroNum += cover2.CoverZeroNum;
        setRow.insert(cover2.setRow.begin(),cover2.setRow.end());
        setCol.insert(cover2.setCol.begin(),cover2.setCol.end());
    }
};

template <typename T>
class Mat
{
    size_t m_row{},m_col{};
    std::vector<T> data;
public:
    Mat() = default;
    size_t row(){return m_row;}
    size_t col(){return m_col;}
    explicit Mat(size_t shape1,size_t shape2) {
        m_row = shape1;
        m_col = shape2;
        data.resize(shape1*shape2);
    }
    explicit Mat(size_t shape1,size_t shape2,T value) {
        m_row = shape1;
        m_col = shape2;
        data.resize(shape1*shape2,value);
    }
    Mat (const Mat & mat2){
        data = mat2.data;
        m_row = mat2.m_row;
        m_col = mat2.m_col;
    }

    Mat & operator = (const Mat & mat2){
        if(&mat2 == this){
            return *this;
        }else {
        data = mat2.data;
        m_row = mat2.m_row;
        m_col = mat2.m_col;
        }
    }

    void initialize(const std::vector<int> & vec)
    {
        for(int i = 0; i < m_row; i ++ ){
            for(int j = 0; j < m_col ; j++)
                data[i*m_col+j] = vec[i*m_col+j];
        }
    }


    void clear(int value = 0) { data = value; }
    T& operator()(int x) { return data[x]; }
    T& operator()(int x, int y) { return data[x * m_col + y]; }

//    std::slice_array<T> diagonal()
//    {
//        assert(m_col == m_row);
//        return data[std::slice(0, m_col, m_col + 1)];
//    }
//
//    std::slice_array<T> row(std::size_t row)
//    {
//        return data[std::slice(m_col * row, m_col, 1)];
//    }
//    std::slice_array<T> col(std::size_t col)
//    {
//        return data[std::slice(col, m_row,m_col)];
//    }

    void print()
    {
        std::cout << "-----------------------------\n";
        for(int i = 0; i < m_row; i ++ ){
            std::cout << "[";
            for(int j = 0; j < m_col ; j++){
                if (j != m_col-1) {
                    std::cout << data[i * m_col + j] << ",";
                }else {
                    std::cout << data[i * m_col + j] << "]\n";
                }
            }
        }
    }

    Mat<T> RowMax()
    {
        // 计算每一行的最大值
        Mat<T> maxmat(m_row,1);
        for(int i = 0 ;i < m_row ; i++){
            maxmat.data[i] = operator()(i,0);
            for(int j = 0; j < m_col; j++){
                if( maxmat.data[i] < operator()(i,j) ){
                    maxmat.data[i] = operator()(i,j);
                }
            }
        }
        return maxmat;
    }
    Mat<T> RowMin()
    {
        // 计算每一行的最大值
        Mat<T> minmat(m_row,1);
        for(int i = 0 ;i < m_row ; i++){
            minmat.data[i] = operator()(i,0);
            for(int j = 0; j < m_col; j++){
                if( minmat.data[i] > operator()(i,j) ){
                    minmat.data[i] = operator()(i,j);
                }
            }
        }
        return minmat;
    }

    Mat<T> ColMax()
    {
        // 计算每一行的最大值
        Mat<T> maxmat(1,m_col);
        for(int i = 0 ;i < m_col ; i++){
            maxmat.data[i] = operator()(0,i);
            for(int j = 0; j < m_row; j++){
                if( maxmat.data[i] < operator()(j,i) ){
                    maxmat.data[i] = operator()(j,i);
                }
            }
        }
        return maxmat;
    }
    Mat<T> ColMin()
    {
        // 计算每一行的最大值
        Mat<T> minmat(1, m_col);
        for(int i = 0 ;i < m_col ; i++){
            minmat.data[i] = operator()(0, i);
            for(int j = 0; j < m_row; j++){
                if(minmat.data[i] > operator()(j, i) ){
                    minmat.data[i] = operator()(j, i);
                }
            }
        }
        return minmat;
    }



    template<typename Func>
    void apply( Func func,size_t pos,bool isRow = true)
    {
        // apply函数,原地修改
        if(isRow){
            for(int i = 0; i< m_col; i++){
                data[pos*m_col + i] = func(data[pos*m_col + i]);
            }
        }else{
            for(int i = 0; i< m_row; i++){
                data[pos + i*m_col] = func(data[pos + i*m_col]);
            }
        }
    }

    size_t countZero()
    {
        // 统计矩阵中的所有零元素
        size_t count = 0;
        for(int i = 0;i < m_row ;i++){
            for(int j = 0; j < m_col ;j ++){
                if(operator()(i,j) == 0 ){
                    count ++;
                }
            }
        }
        return count;
    }

    Cover detectZero()
    {
        // 检测所有的0,首先返回的是行,接着放回的是列
        Cover cover;
        std::array<std::vector<T>,2> res;
        res[0] = detectZero(true);
        res[1] = detectZero(false);
        int posx = std::max_element(res[0].begin(),res[0].end()) - res[0].begin();
        int posy = std::max_element(res[1].begin(),res[1].end()) - res[1].begin();
        T max_x = res[0][posx];
        T max_y = res[1][posy];
        int isRow = (max_x > max_y ? 1 : -1);
        if(isRow > 0){
            cover.setRow.insert(posx);
            cover.CoverZeroNum = max_x;

        }else{
            cover.setCol.insert(posy);
            cover.CoverZeroNum = max_y;
        }
        return cover;
    }



    std::vector<int> detectZero(bool isRow)
    {
        // 检测每一行(列)上零元素的个数
        if(isRow){
            std::vector<int> res(m_row,0);
            for(int i = 0;i < m_row ;i++){
                for(int j = 0; j < m_col ;j ++){
                    if(operator()(i,j) == 0 ){
                        res[i] ++;
                    }
                }
            }
            return res;
        }else{
            std::vector<int> res(m_col,0);
            for(int i = 0;i < m_col ;i++){
                for(int j = 0; j < m_row ;j ++){
                    if(operator()(j,i) == 0 ){
                        res[i] ++;
                    }
                }
            }
            return res;
        }
    }

    size_t Count()
    {
        // 计算0元素的个数
        size_t count = 0;
        for(int i = 0; i < m_row; i++){
            for(int j = 0; j < m_col; j++){
                if(operator()(i,j) == 0){
                    count ++;
                }
            }
        }
        return count;
    }

    Mat<T> reduce(const std::set<T> & setx,const std::set<T> & sety)
    {
        int reduce_x = setx.size(),reduce_y = sety.size();
        std::vector<int> vx(m_row),vy(m_col);
        std::iota(vx.begin(), vx.end(),0);
        std::iota(vy.begin(),vy.end(),0);

        std::vector<int> diff_x,diff_y;
        std::set_difference(vx.begin(),vx.end(),setx.begin(),setx.end(),std::back_inserter(diff_x));
        std::set_difference(vy.begin(),vy.end(),sety.begin(),sety.end(),std::back_inserter(diff_y));
        // 计算得到去除 setx,sety中的向量


        Mat<T> mat(m_row-reduce_x,m_col-reduce_y);

        for(int i = 0; i < mat.m_row; i++){
            for(int j = 0; j < mat.m_col;j++){
               mat(i,j) = operator()(diff_x[i],diff_y[j]);
            }
        }

        return mat;
    }


//    Mat<T> reduce(int pos , bool isRow)
//    {   // 矩阵缩减,减少某一行或者某一列
//        if(isRow){
//            Mat<T> mat(m_row-1,m_col);
//            for(int i = 0; i < m_row; i++){
//                if(i == pos) {continue;}
//                for(int j = 0; j < m_col ;j++){
//                    mat(i,j) = operator()(i,j);
//                }
//            }
//            return mat;
//        }else{
//          Mat<T> mat(m_row,m_col - 1);
//            for(int i = 0; i < m_col; i++){
//                if(i == pos) {continue;}
//                for(int j = 0; j < m_row ;j++){
//                    mat(j,i) = operator()(j,i);
//                }
//            }
//          return mat;
//        }
//    }

    void CoverZero(Cover & Regard)
    {   // Regard是需要上一次输入变量,需要忽视的地方
        // 找到Regard之外的地方,找到最大值和最小值的覆盖 加入到Regrad中,如此循环
        // 知道覆盖所有的零
        print();
        auto [diff_x,diff_y] = Regard.diff();
        // 先从行上进行遍历
        std::vector<int> detectZeroRow( m_row,0);
        for(int & i : diff_x){
            for(int & j : diff_y){
                if(operator()(i,j) == 0){
                    detectZeroRow[i] ++;
                }
            }
        }
        // 再从列上进行遍历
        std::vector<int> detectZeroCol( m_col,0);
        for(int & i : diff_x){
            for(int & j : diff_y){
                if(operator()(i,j) == 0){
                    detectZeroCol[j] ++;
                }
            }
        }
        // 比较两个中最大的,然后将最大的位置插入到Cover中
        int posx = std::max_element(detectZeroRow.begin(),detectZeroRow.end()) - detectZeroRow.begin();
        int posy = std::max_element(detectZeroCol.begin(),detectZeroCol.end()) - detectZeroCol.begin();

        T max_x = detectZeroRow[posx];
        T max_y = detectZeroCol[posy];


        if(max_x > max_y){
            Regard.setRow.insert(posx);
            Regard.CoverZeroNum += max_x;
        }else{
            Regard.setCol.insert(posy);
            Regard.CoverZeroNum += max_y;
        }
    }


    Cover minimumSetCoveringZeros()
    {
        Cover cover(m_row,m_col);
        int ZeroCount = countZero();
        while(cover.CoverZeroNum < ZeroCount){
            CoverZero(cover);
        }
        return cover;
    }

    void addZero(const Cover & cover ) //添加矩阵中的零元素
    {
        /* 分以下三步
         * 1. 计算非覆盖区域的最小值,
         * 2. 非覆盖区域减去这个最小值
         * 3. 覆盖的交点上加上这个最小值
        */
        auto [diff_x,diff_y] = cover.diff();
        int minvalue;
        minvalue = operator()(diff_x[0],diff_y[0]);
        for(auto &i : diff_x){
            for(auto & j : diff_y){
                if(minvalue > operator()(i,j)){
                    minvalue = operator()(i,j);
                }
            }
        }
        // 减去最小值
        for(auto &i : diff_x){
            for(auto & j : diff_y){
                operator()(i,j) -= minvalue;
            }
        }
        // 交叉的地方加上最小值
        for(auto i : cover.setRow){
            for(auto j :cover.setCol){
                operator()(i,j) += minvalue;
            }
        }


    }

//    std::vector<int> Match()
//    {
//        std::vector<int> res(m_col,0);
//        for(auto x : cover.setRow){
//            for(int j = 0;j < m_col;j ++){
//                if(cover.setCol.find(j) == cover.setCol.end()){ //j指标不在setCol中,取出元素
//                    res[x] = j;
//                }
//            }
//        }
//
//        for(auto y : cover.setCol){
//            for(int j = 0;j < m_row;j ++){
//                if(cover.setRow.find(j) == cover.setRow.end()){ //j指标不在setCol中,取出元素
//                    res[j] = y;
//                }
//            }
//        }
//        return res;
//    }
    void cartesianProduct(const std::vector<std::vector<int>>& sets,
                          std::vector<int>& current,
                          int depth,
                          std::vector<std::vector<int>>& result) {
        if (depth == sets.size()) {
            // 如果深度等于集合数量，说明已经生成了一个完整的组合
            result.push_back(current);
            return;
        }

        for (int i = 0; i < sets[depth].size(); ++i) {
            // 选择当前深度的一个元素
            current.push_back(sets[depth][i]);
            // 递归到下一个深度
            cartesianProduct(sets, current, depth + 1, result);
            // 回溯，移除当前选择的元素
            current.pop_back();
        }
    }

// 主函数来调用递归函数
    std::vector<std::vector<int>> cartesianProduct(const std::vector<std::vector<int>>& sets) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        cartesianProduct(sets, current, 0, result);
        return result;
    }
    std::vector<int> Match()
    {
        std::vector<std::vector<T>> RowZeroPos(m_row); //表示横轴上取值为0的索引
        for(int i = 0; i < m_row;i ++){
            for(int j = 0;j < m_col ;j ++){
                if(operator()(i,j) == 0){
                    RowZeroPos[i].push_back(j);
                }
            }
        }
        //print();
        // 获取笛卡尔积
        std::vector<std::vector<int>> result = cartesianProduct(RowZeroPos);
        for (auto vec : result) {
            std::set<int> x(vec.begin(),vec.end());
            if(x.size() == vec.size()){ //去重
                return vec;
            }
        }
        print();
        std::cerr << "没有匹配的算法\n";
        // 打印结果
        // 打印结果
//        for (const auto& vec : result2) {
//            for (int num : vec) {
//                std::cout << num << " ";
//            }
//            std::cout << std::endl;
//        }
//        std::cout << "原始向量大小 " << result.size() << ", 去重后向量大小 :" << result2.size();

    }


};



